﻿#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <math.h>

////输入数字 n ，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3 ，则打印出 1、2、3 一直到最大的 3 位 数 999 。
////用返回一个整数列表来代替打印
////n 为正整数
//int main() {
//	int a = 1, n = 0;
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++) {
//		a *= 10;
//	}
//	printf("%d", a);
//	return 0;
//}

////#define 与 tpyedef
//#define INT_PTR int* //直接替换
//typedef int* int_ptr; 
//INT_PTR a, b; // == int *a,b; == int *a;int b;
//int_ptr c, d; // == int *c,*d;

////输入一行，每行空格分割，分别是年，月，日
////输出是这一年的第几天
//int main() {
//    int year = 0, month = 0, day = 0;
//    scanf("%d%d%d", &year, &month, &day);
//    //初始化月份
//    int arr_month[] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
//    //判断闰年
//    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
//        arr_month[1] = 29;
//    }
//    //求month之前的月份天数和
//    int sum = 0;
//    for (int i = 0; i < month - 1; i++) {
//        sum = sum + arr_month[i];
//    }
//    sum = sum + day;
//    printf("%d", sum);
//    return 0;
//}



////验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。
////例如：
////1 ^ 3 = 1
////2 ^ 3 = 3 + 5
////3 ^ 3 = 7 + 9 + 11
////4 ^ 3 = 13 + 15 + 17 + 19
////输入一个正整数m（m≤100），将m的立方写成m个连续奇数之和的形式输出。
//int maim() {
//    int n = 0;
//    scanf("%d", &n);
//    int num = n * n - (n / 2 * 2);
//    //如果是偶数+1
//    if (num % 2 == 0) {
//        num++;
//    }
//    for (int i = 0; i < n; i++) {
//        printf("%d", num);
//        if (i < n - 1) {
//            printf("+");
//        }
//    }
//
//    return 0;
//}

////等差数列 2，5，8，11，14。。。。
////（从 2 开始的 3 为公差的等差数列）
////输出求等差数列前n项和
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    int sum = 2;
//    int num = 2;
//    for (int i = 1; i < n; i++) {
//        \
//            //求当前数
//            num += 3;
//        //求和
//        sum += num;
//    }
//    printf("%d", sum);
//    return 0;
//}

////首先输入一个正整数n，
////然后输入n个整数。
////输出负数的个数，和所有正整数的平均值。
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    int i = 0;
//    int num = 0;
//    //负数的数量
//    int count = 0;
//    //0的数量
//    int zero = 0;
//    double sum = 0.0;
//    for (i = 0; i < n; i++) {
//        scanf("%d", &num);
//        if (num > 0) {
//            sum += num;
//        }
//        else if (num < 0) {
//            count++;
//        }
//        else {
//            zero++;
//        }
//    }
//    if (sum == 0) {
//        printf("%d %.1lf", count, sum);
//    }
//    else {
//        printf("%d %.1lf", count, sum / (n - count - zero));
//    }
//    return 0;
//}

////有一个长度为 n 的非降序数组，比如[1, 2, 3, 4, 5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组
////比如变成了[3, 4, 5, 1, 2]，或者[4, 5, 1, 2, 3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
///**
// *
// * @param rotateArray int整型一维数组
// * @param rotateArrayLen int rotateArray数组长度
// * @return int整型
// *
// * C语言声明定义全局变量请加上static，防止重复定义
// */
//int minNumberInRotateArray(int* rotateArray, int rotateArrayLen) {
//    int min = *rotateArray;
//    for (int i = 1; i < rotateArrayLen; i++) {
//        if (min > *(rotateArray + i)) {
//            min = *(rotateArray + i);
//        }
//    }
//    return min;
//}




////集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
////给定一个数组 nums 代表了集合 S 发生错误后的结果。
////请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
//int ret[2];
//int* findErrorNums(int* nums, int numsSize, int* returnSize) {
//    //由题知返回的数组元素个数为2
//    *returnSize = 2;
//    int arr[numsSize + 1];
//    int original_sum = 0;
//    int lost_sum = 0;
//    for (int i = 0; i < numsSize; i++) {
//        //如果找到一个相同的数，发现它已经被标记过，那么代表重复
//        if (arr[nums[i]] == 1) {
//            //把重复的数放入ret[0]
//            ret[0] = nums[i];
//        }
//
//        //当找到一个数，把它放入arr数组中,使其在arr中的下标等于其值
//        //然后在arr中标记为1，代表该位置已经有数据了
//        arr[nums[i]] = 1;
//
//        //接下来需要找到丢失的数字
//        //分别对原始数组和出错的数组求和，它们的差值即为丢失数据和重复数据的差值
//        original_sum += i + 1;
//        lost_sum += nums[i];
//    }
//    //ret[1] - ret[0] = orignial_sum - lost_sum
//    ret[1] = original_sum - lost_sum + ret[0];
//    return ret;
//}


////小明同学最近开发了一个网站，在用户注册账户的时候，需要设置账户的密码，为了加强账户的安全性，小明对密码强度有一定要求：
////1. 密码只能由大写字母，小写字母，数字构成；
////2. 密码不能以数字开头；
////3. 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；
////4. 密码长度至少为8
////现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。
////
////输入描述：
////输入一个数n，接下来有n(n≤100)行，每行一个字符串，表示一个密码，输入保证字符串中只出现大写字母，小写字母和数字，字符串长度不超过100。
////输出描述：
////输入n行，如果密码合法，输出YES，不合法输出NO
//
//int main() {
//    char password[100];
//    int i = 0;
//    //n组输入
//    int n = 0;
//    scanf("%d", &n);
//    while (n) {
//        //输入
//        scanf("%s", password);
//        //判断一组密码是否合格
//        //先判断密码长度至少为8
//        //当大于等于8进行下一项判断，否则不合格
//        int len = strlen(password);
//        if (len >= 8) {
//            for (i = 0; i < len; i++) {
//                //当首元素为字母，继续
//                if ('a' <= password[0] <= 'z' || 'A' <= password[0] <= 'Z') {
//                    //如果符合，继续该字符串下一元素的判断，不符合输出NO，并且中止该字符串的判断
//                    if (0 <= password[i] <= 9 || 'a' <= password[i] <= 'z' || 'A' <= password[i] <= 'Z') {
//
//                    }
//                    else {
//                        printf("NO\n");
//                        break;
//                    }
//                }
//            }
//            //全部合格输出YES
//            printf("YES\n");
//        }
//        else {
//            printf("NO\n");
//        }
//        n--;
//    }
//
//    return 0;
//}


////给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
///**
// *
// * @param data int整型一维数组
// * @param dataLen int data数组长度
// * @param k int整型
// * @return int整型
// *
// * C语言声明定义全局变量请加上static，防止重复定义
// */
//int GetNumberOfK(int* data, int dataLen, int k) {
//    // write code here
//    static int count = 0;
//    for (int i = 0; i < dataLen; i++) {
//        if (data[i] == k) {
//            count++;
//        }
//    }
//    return count;
//}


////整数转换。编写一个函数，确定需要改变几个位才能将整数 A 转成整数 B 。
//int convertInteger(int A, int B) {
//    //找到不同位的个数
//    int tmp = A ^ B;
//    //tmp中1的个数即为需要改变的位的个数
//    int count = 0;
//    for (int i = 0; i < 32; i++) {
//        if ((tmp >> i) & 1 == 1) {
//            count++;
//        }
//    }
//    return count;
//}


////给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
////请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 - 1 。
//int dominantIndex(int* nums, int numsSize) {
//    int max = 0, second = 0;
//    int max_num = 0;
//    int min = *nums;
//    int i = 0;
//    //找最小
//    for (i = 0; i < numsSize; i++) {
//        if (nums[i] < min) {
//            min = nums[i];
//        }
//    }
//    max = min;
//    second = min;
//    //找最大
//    for (i = 0; i < numsSize; i++) {
//        if (nums[i] > max) {
//            max = nums[i];
//            max_num = i;
//        }
//    }
//    //找第二大
//    for (i = 0; i < numsSize; i++) {
//        if (nums[i] > second && nums[i] < max) {
//            second = nums[i];
//        }
//    }
//    if (max >= second * 2 || second == 0) {
//        return max_num;
//    }
//    else {
//        return -1;
//    }
//    
//}
//int main() {
//    int arr[] = { 3,6,1,0 };
//    printf("%d",dominantIndex(arr, 4));
//    return 0;
//}

////给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
//int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
//    static int arr[1000];
//    int i = 0, j = 0, x = 0;
//    *returnSize = 0;
//    //遍历nums1
//    for (i = 0; i < nums1Size; i++) {
//        //遍历nums2
//        for (j = 0; j < nums2Size; j++) {
//            //当找到相同的数，再对arr中的元素进行遍历，查看是否已经有该数
//            if (nums2[j] == nums1[i]) {
//                //在arr中检查是否已经存在
//                int tmp = 0;
//                for (x = 0; x < *returnSize; x++) {
//                    //如果已经存在，tmp=1
//                    if (arr[x] == nums1[i]) {
//                        tmp = 1;
//                    }
//                }
//                //当不存在，tmp仍为0，此时进行赋值
//                if (tmp == 0) {
//                    arr[*returnSize] = nums1[i];
//                    *returnSize += 1;
//                }
//            }
//        }
//    }
//
//    return arr;
//}

////对字符串中的内容按ASCII码值排序
//int main() {
//    char str[1000];
//    scanf("%s", str);
//    int len = strlen(str);
//    int i = 0, j = 0;
//    //冒泡排序
//    for (j = 0; j < len - 1; j++) {
//        for (i = 0; i < len - 1 - j; i++) {
//            if (str[i] > str[i + 1]) {
//                int tmp = str[i];
//                str[i] = str[i + 1];
//                str[i + 1] = tmp;
//            }
//        }
//    }
//    printf("%s", str);
//    return 0;
//}



////给你一个整数数组 nums ，请计算数组的 中心下标 。
////数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
////如果中心下标位于数组最左端，那么左侧数之和视为 0 等于右侧数之和，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
////如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 - 1 。
//int pivotIndex(int* nums, int numsSize) {
//	  //中心下标为n
//    int n = 0;
//    int i = 0;
//    //从左往右遍历
//    //先计算从左往右arr[0]~arr[n-1]之和以及剩下arr[n+1]~arr[numsSize-1]个元素之和
//    //当left之和小于right之和，n++
//    //当相等，返回n
//    //当left之和大于right之和，不存在中心下标，返回-1
//    while (n < numsSize) {
//        int left = 0;
//        int right = 0;
//        for (i = 0; i < n; i++) {
//            left += nums[i];
//        }
//        for (i = n + 1; i < numsSize; i++) {
//            right += nums[i];
//        }
//        if (left == right) {
//            return n;
//        }//当n == numsSize-1，且left == 0，中心下标位于最右侧
//        else if (n == numsSize - 1 && left == 0) {
//            return n;
//        }//当right == 0，且n=0，中心下标位于做左侧
//        else if (right == 0 && n == 0) {
//            return 0;
//        }
//        n++;
//    }
//    //当没有中心下标，返回-1
//    return -1;
//}
//
//int main() {
//    int arr[] = { 1,2,3 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    printf("%d",pivotIndex(arr, sz));
//    return 0;
//}


////编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内(0~127 ，包括 0 和 127)，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
////例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
////数据范围：1≤n≤500
////输入描述：
////输入一行没有空格的字符串。
////输出描述：
////输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。
//int main() {
//    char str[500], arr[128];
//    scanf("%s", str);
//    //遍历str和arr，把str中arr所没有的字符添加到arr中
//    int i = 0;
//    int len = strlen(str);
//    arr[0] = str[0];
//    //遍历str，找到一个字符
//    for (i = 0; i < len; i++) {
//        int j = 0;
//        int len_arr = strlen(arr);
//        //tmp用于判断arr中是否有该字符
//        int tmp = 0;
//        while (j < len_arr) {
//            //如果arr中已经有了该字符，tmp=1
//            if (str[i] == arr[j]) {
//                tmp = 1;
//                break;
//            }
//            j++;
//        }
//        //当arr中没有该字符，把这个字符写入arr
//        if (tmp == 0) {
//            //arr中的字符个数本来为len_arr，所以尾元素为arr[len_arr-1]
//            arr[len_arr] = str[i];
//            //当新的字符被写入arr,len_arr也会增加
//        }
//    }
//    printf("%d", strlen(arr));
//    return 0;
//}


////一个数组中有一个数字出现次数大于 n / 2 ，从第 0 个字符开始，假设它就是最多的那个数字，遇到相同的数字则计
////数 + 1 ， 遇到不同的则计数 - 1 ，其实就是互相消耗，等到计数为 0 的时候，表示本次互拼完毕，从下一个字符重新开
////始互拼，但是归根结底出现次数大于 n / 2 的这个数字数量更多，因此也是最后保留的字符。
////示例： "23335" 首先从字符 2 开始计数 1 ，遇到 3 ，不同则 - 1 ，互拼消耗 重新从剩下的 "335" 开始的过程
////这时候保存的字符为 3 ，遇到 3 则计数 + 1 ， 遇到5则计数 - 1 ，在计数不为 0 时，走到末尾保存的字符就是个数超过 n / 2的字符
//int majorityElement(int* nums, int numsSize) {
//    int count = 1;
//    int num = *nums;
//    for (int i = 1; i < numsSize - 1; i++) {
//        if (nums[i] == num) {
//            count++;
//        }
//        else {
//            count--;
//        }
//        if (count == 0) {
//            num = nums[i + 1];
//            //可以加上后面的，逻辑是使num=nums[i+1]，count重新记为1，接下来从nums[i+2]进行对比
//            //如果不加后面的则为使num=nums[i+1]，从nums[i+1]进行对比，此时两者相等，count记为1
//            //count = 1;
//            //i++;
//            
//        }
//    }
//    return num;
//}


////自除数 是指可以被它包含的每一位数整除的数。
////例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
////自除数 不允许包含 0 。
////给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。
//int* selfDividingNumbers(int left, int right, int* returnSize) {
//    int i = 0;
//    static int arr[10000];
//    int n = 0;
//    for (i = left; i <= right; i++) {
//        int tmp = i;
//        while (tmp) {
//            //i不能是10的倍数，且i要被tmp%10整除
//            if (tmp % 10 == 0 || i % (tmp % 10) != 0) {
//                break;
//            }
//            else {
//                tmp /= 10;
//            }
//            if (tmp == 0) {
//                arr[n] = i;
//                n++;
//            }
//        }
//    }
//    *returnSize = n;
//    return arr;
//}


////给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
////题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
////请不要使用除法，且在 O(n) 时间复杂度内完成此题
////复杂度为O(n^2)
//int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//    static int answer[100000];
//    int i = 0, j = 0;
//    for (i = 0; i < numsSize; i++) {
//        int tmp = 1;
//        for (j = 0; j < numsSize; j++) {
//            if (i != j) {
//                tmp *= nums[j];
//            }
//        }
//        answer[i] = tmp;
//    }
//    *returnSize = numsSize;
//    return answer;
//}

//int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//    static int answer[100000];
//    int left = 1, right = 1;
//    int i = 0, j = 0;
//    for (i = 0; i < numsSize; i++) {
//        //计算answer[i]左侧所有元素的乘积，并把乘积存入answer[i]
//        //把left的值赋给answer[i]，因为当i=0时，左侧没有数，只计算右侧的乘积=1*right
//        answer[i] = left;   //1 nums[0] nums[0]*nums[1] nums[0]*nums[1]*nums[2]……
//        left *= nums[i];    //nums[0] nums[0]*nums[1] nums[0]*nums[1]*nums[2]……
//    }
//    for (i = numsSize - 1; i >= 0; i--) {
//        //此时在answer[i]的基础上乘以answer[i]右侧所有元素的乘积right
//        //同理当i = numsSize - 1时，right=1，只用计算左侧的乘积
//        answer[i] *= right;
//        right *= nums[i];
//    }
//
//    *returnSize = numsSize;
//    return answer;
//}

//x = -1
//原 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
//反 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111110
//补 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

//-1 - 1 = -2
//原 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000010
//反 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111101
//补 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111110

//-1 & -2 = -2
//   11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111110

//-2 - 1 = -3
//原 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000011
//反 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111100
//补 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111101

//-2 & -3 = 
//   11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111100


////写一个函数，求两个整数之和，要求在函数体内不得使用 + 、 - 、 * 、 / 四则运算符号。
//int Add(int num1, int num2) {
//    //拆成不进位 + 进位
//    //当进位为0得到相加之和
//    while (num2) {
//        //tmp为不考虑进位的相加结果
//        //a^b = 不进位的相加结果
//        //5^7 = 2
//        int tmp = num1 ^ num2;
//        //num2为进位,因为进位所以要左移一位
//        //a&b为进位，5^7 = 5, 5 << 1 = 10
//        num2 = (num1 & num2) << 1;
//        //num1为不进位
//        num1 = tmp;
//    }
//    return num1;
//}


//int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
//    //建一个数组存放1~numsSize
//    static int arr[100000];
//    //static int ret[100000];
//    int i = 0;
//    for (i = 0; i < numsSize; i++) {
//        arr[i] = i + 1;
//    }
//    //遍历nums[]和arr[]，在arr[]中当找到nums中的数字，该元素置为0
//    *returnSize = 0;
//    for (i = 0; i < numsSize; i++) {
//        for (int j = 0; j < numsSize; j++) {
//            if (arr[i] == nums[j]) {
//                arr[i] = 0;
//            }
//        }
//    //    //当arr[i]不为0，即nums中没有等于arr[i]的数，把该数赋给ret[n]
//    //    if (arr[i] != 0) {
//    //        ret[*returnSize] = arr[i];
//    //        *returnSize += 1;
//    //    }
//    //}
//    //return ret;
//
//        //因为i始终 >= i，所以也可把arr[i]赋给arr[*returnSize],最后返回arr
//          if (arr[i] != 0) {
//           arr[*returnSize] = arr[i];
//           *returnSize += 1;
//        }
//    }
//    return arr;
//}

//例如nums = {4,3,2,7,8,2,3,1};
//其下标index=0 1 2 3 4 5 6 7
//首先从 0 ~ numsSize-1 进行遍历
//找到nums[0] = 4 ，那么把第 4 个元素标记一下，即nums[3] = -nums[3]
//在nums[1] = 3，那么把第 3 个元素标记一下，即nums[2] = -nums[2]
//只有当第nums[i]个元素为正的时候才标记，为负代表已经标记过，不再重新标记

//最后标记完之后的nums = {-4,-3,-2,-7, 8, 2,-3,-1}
//其下标index =			 0  1  2  3  4  5  6  7

//最后遍历nums，当nums[i] > 0，把 i+1 写入 arr（ nums[i]为 第i+1 个元素 ）

//int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
//    //遍历nums，每当遍历一次nums[i],就把下标为 nums[i]-1 的元素标记一下，代表i存在数组中
//    //例如nums[3] = 6，则标记第6个元素，第6个元素下标index = 5 = nums[i]-1
//    //nums[index] = -nums[index]即nums[5] = -nums[5]
//
//    //这里使用负数标记，当i未被标记过，即nums[i]>0，index = nums[i]-1，nums[index] = -nums[index]
//    //若i已经被标记过，即nums[i]<0，index = -(nums[i])-1，nums[index] = -nums[index]
//
//    //当i已经被标记，nums[i]<0，此时需要使index = (-nums[i])-1
//    //当最终标记完，如果第n个元素没有被标记，那么n即为没有出现过的数字，n = 没有被标记的元素的下标+1
//    int i = 0;
//    static int arr[100000];
//    *returnSize = 0;
//    for (i = 0; i < numsSize; i++) {
//        int index = 0;
//        if (nums[i] > 0) {
//            //标记第nums[i]个元素，该元素下标index = nums[i]-1
//            index = nums[i] - 1;
//        }
//        else {
//            index = -(nums[i]) - 1;
//        }
//        //当nums[index]未被标记即 nums[index]>0，才置为-1
//        //若nums[index]<0，代表已经被标记过，不重新标记
//        if (nums[index] > 0) {
//            nums[index] = -nums[index];
//        }
//    }
//    //最后如果第n个元素未被标记，即该元素的值>0，那么该数组中就没有n这个数组
//    //第n个元素的下标index为n-1
//    //最后遍历一次数组，把n写入返回数组
//    for (i = 0; i < numsSize; i++) {
//        if (nums[i] > 0) {
//            arr[*returnSize] = i + 1;
//            *returnSize += 1;
//        }
//    }
//    return arr;
//}
//
//int main() {
//    int nums[] = { 1,2,3,4,5,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
//    int numsSize = sizeof(nums) / sizeof(nums[0]);
//    int sz = 0;
//    int *returnSize = &sz;
//    int* tmp = findDisappearedNumbers(nums, numsSize, returnSize);
//    int i = 0;
//    for (i = 0; i < sz; i++) {
//        printf("%d ",tmp[i] );
//    }
//    return 0;
//}


////给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
//int findMaxConsecutiveOnes(int* nums, int numsSize) {
//    int count = 0;
//    int tmp = 0;
//    for (int i = 0; i < numsSize; i++) {
//        tmp++;
//        if (nums[i] != 1) {
//            tmp = 0;
//        }
//        if (count < tmp) {
//            count = tmp;
//        }
//    }
//    return count;
//}

////
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    int sum = 0;
//    int count = 0;
//    int i = 0, j = 0;
//    for (i = 2; i <= n; i++) {
//        //重置sum
//        sum = 0;
//        for (j = 1; j <= i / 2; j++) {
//            //找到约数
//            if (i % j == 0) {
//                sum = sum + j;
//            }
//        }
//        if (sum == i) {
//            count++;
//            printf("%d ", sum);
//        }
//    }
//    printf("\n\ncount = %d", count);
//    return 0;
//}
 

////求输出n以内(含n)完全数的个数。完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
////它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
////例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1 + 2 + 4 + 7 + 14 = 28。
//int main() {
//	int n = 0;
//	scanf("%d", &n);
//    int j = 0;
//    int sum = 0;
//    for (j = 1; j <= n / 2; j++) {
//        //找到约数
//        if (n % j == 0) {
//            printf("%d ", j);
//            sum = sum + j;
//        }
//    }
//    printf("\n%d", sum);
//}


////输入一个整数，将这个整数以字符串的形式逆序输出
////程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    char arr[100000];
//    int i = 0;
//    if (n == 0) {
//        arr[i] = n;
//        printf("%c", arr[i]+'0');
//    }
//    while (n != 0) {
//        arr[i] = n % 10;
//        n /= 10;
//        printf("%c", arr[i]+'0');
//        i++;
//    }
//
//    return 0;
//}

////对字符串中的所有字符进行倒排。
//void reverse(char str[], int len) {
//    int i, j = 0;
//    for (i = len - 1; i >= 0; i--) {
//        //使i指向末尾单词的左侧
//        //当i遇到空格，j=i+1，当j<len-i，从左向右开始打印
//        //当j遇到空格或者\0，停止打印
//        //打印完成后i 指向 左一个单词，重复如上步骤
//        if (str[i] == ' ') {
//            //此处只是约数j不越界
//            for (j = i + 1; j <= len; j++) {
//                //当遇到空格或者\0，打印一个空格后退出循环
//                if (str[j] == ' ' || str[j] == '\0') {
//                    printf(" ");
//                    break;
//                }
//                printf("%c", str[j]);
//            }
//            //因为有多个空格也只打印一个空格，若i指向空格，需要使i--直到不指向空格
//            while (str[i] == ' ') {
//                i--;
//            }
//        }
//        //当i指向字符串首元素时，打印完首单词后不打印空格
//        if (i == 0) {
//            for (j = i; j < len; j++) {
//                //当遇到空格或者\0，打印一个空格后退出循环
//                if (str[j] == ' ' || str[j] == '\0') {
//                    break;
//                }
//                printf("%c", str[j]);
//            }
//        }
//    }
//
//
//}
// 

////对字符串中的所有单词进行倒排。
//void reverse2(char str[], int len) {
//    int i, j = 0;
//    for (i = len - 1; i >= 0; i--) {
//        //使i指向末尾单词的左侧
//        //当i遇到非字母，j=i+1，当j<len-i，从左向右开始打印
//        //当j遇到非字母，停止打印
//        //打印完成后i 指向 左一个单词，重复如上步骤
//        if (str[i] == ' ' ||
//            str[i] == '\0' ||
//            str[i] < 'A' ||
//            (str[i] > 'Z' && str[i] < 'a') ||
//            str[i]>'z') {
//            //此处只是约数j不越界
//            for (j = i + 1; j <= len; j++) {
//                //当遇到字母以外的字符，打印一个空格后退出循环
//                if (str[j] == ' ' ||
//                    str[j] == '\0' ||
//                    str[j] < 'A' ||
//                    (str[j] > 'Z' && str[j] < 'a') ||
//                    str[j]>'z') {
//                    printf(" ");
//                    break;
//                }
//                printf("%c", str[j]);
//            }
//            //因为有多个空格也只打印一个空格，若i指向空格，需要使i--直到不指向空格
//            while (str[i] == ' ') {
//                i--;
//            }
//        }
//        //当i指向字符串首元素时，打印完首单词后不打印空格
//        if (i == 0) {
//            for (j = i; j < len; j++) {
//                //当遇到字母以外的字符，打印一个空格后退出循环
//                if (str[j] == ' ' ||
//                    str[j] == '\0' ||
//                    str[j] < 'A' ||
//                    (str[j] > 'Z' && str[j] < 'a') ||
//                    str[j]>'z') {
//                    printf(" ");
//                    break;
//                }
//                printf("%c", str[j]);
//            }
//        }
//    }
//
//}

//
//int main() {
//    char str[10000];
//    gets_s(str,10000);
//    int len = strlen(str);
//    reverse(str, len);
//    return 0;
//}


////有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
////例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
////一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
////斐波那契数列
//int fib(int n) {
//    if (n == 1 || n == 2) {
//        return 1;
//    }
//    else {
//        return fib(n - 1) + fib(n - 2);
//    }
//}
//
//int fib2(int n) {
//    int a = 1, b = 1, c = 1;
//    while (n > 2) {
//        c = a + b;
//        a = b;
//        b = c;
//        n--;
//    }
//}
//
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    printf("%d", fib(n));
//    return 0;
//}

//int main() {
//	double n, m;
//	while (~scanf("%lf %lf", &n, &m)) {
//		double sum = 0;
//		while (m-- > 0) {
//			sum += n;
//			n = sqrt(n);
//		}
//		printf("%.2lf", sum);
//	}
//	return 0;
//}

////计算机有4个槽，每个槽放一个球，颜色可能是红色（ R ）、黄色（ Y ）、绿色（ G ）或蓝色（ B ）。例如，计算
////机可能有 RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你
////可能会猜 YRGB 。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注
////意，“猜中”不能算入“伪猜中”。
////给定一种颜色组合 solution 和一个猜测 guess ，编写一个方法，返回猜中和伪猜中的次数 answer ，其中 answer[0]
////为猜中的次数， answer[1] 为伪猜中的次数。
//int main() {
//	char solution[] = "GGBB";
//	char guess[] = "RBYB";
//    int i = 0;
//    int arr[] = { 0,0 };
//    //先判断对应位置
//    for (i = 0; i < 4; i++) {
//        //当对应位置颜色相等，猜中+1，并且把guess[i]和solution[i]的内容置为i
//        if (solution[i] == guess[i]) {
//            arr[0] += 1;
//            solution[i] = i;
//            guess[i] = i;
//        }
//    }
//    //再判断不对应位置
//    for (i = 0; i < 4; i++) {
//        int  j = 0;
//        for (j = 0; j < 4; j++) {
//            //当guess[j]和solution[i]颜色相等，把guess[j]和solution[i]的内容置为i
//            if (i != j && guess[j] == solution[i]) {
//                arr[1] += 1;
//                solution[i] = i;
//                guess[j] = i;
//                break;
//            }
//        }
//    }
//    printf("%d %d", arr[0], arr[1]);
//	return 0;
//}



//int* twoSum(int* numbers, int numbersLen, int target, int* returnSize) {
//    // write code here
//    *returnSize = 2;
//    static int arr[2];
//    arr[0] = 0, arr[1] = 0;
//    int i = 0;
//    for (i = 0; i < numbersLen; i++) {
//        //先找到arr[i]，用target-arr[i]得到tmp
//        //这样只需要在数组中找到tmp则说明target可以由数组中的两个数相加得到
//        int tmp = target - numbers[i];
//        //重新遍历除arr[i]以外的元素，找到一个等于tmp的
//        for (int j = i + 1; j < numbersLen; j++) {
//            if (numbers[j] == tmp) {
//                arr[0] = i + 1;
//                arr[1] = j + 1;
//                //找到后结束
//                i = numbersLen;
//                break;
//            }
//        }
//    }
//    return arr;
//}

//int main() {
//	int number[] = { 3,2,4 };
//	int target = 6;
//    int numbersLen = sizeof(number) / sizeof(number[0]);
//    int arr[] = { 0,0 };
//    int i = 0;
//    for (i = 0; i < numbersLen; i++) {
//        //先找到arr[i]，用target-arr[i]得到tmp
//        //这样只需要在数组中找到tmp则说明target可以由数组中的两个数相加得到
//        int tmp = target - number[i];
//        //重新遍历除arr[i]以外的元素，找到一个等于tmp的
//        for (int j = i + 1; j < numbersLen; j++) {
//            if (number[j] == tmp) {
//                arr[0] = i + 1;
//                arr[1] = j + 1;
//                //找到后结束
//                i = numbersLen;
//                break;
//            }
//        }
//    }
//    printf("%d %d", arr[0], arr[1]);
//	return 0;
//}


////求一个数组中出现次数为奇数次的数
// 标记表的方法
//int main() {
//    int n = 0;
//    scanf("%d", &n);
//    int arr[5];
//    int i = 0;
//    int tmp[6];
//    for (i = 0; i <= n; i++) {
//        tmp[i] = 0;
//    }
//    for (i = 0; i < n; i++) {
//        scanf("%d", &arr[i]);
//    }
//    for (i = 0; i < n; i++) {
//        tmp[arr[i]] += 1;
//    }
//    for (i = 1; i <= n; i++) {
//        if (tmp[i] % 2 == 1) {
//            printf("%d ", i);
//        }
//    }
//    return 0;
//}

////异或运算XOR
////采用异或进行计算：1. a ^ a = 0
////				   2. 0 ^ a = a
////					3. x ^ x ^ x ^ y = x ^ y
////异或运算中出现相同的数则会相互抵消
//int main() {
//	int n;
//	while (~scanf("%d", &n)) {
//		int num = 0, tmp = 0; 
//		//对每个数字进行异或，出现偶数次的就会异或为0了，而奇数次刚好剩下的就是对应数字 
//		for (int i = 0; i < n; i++) {
//			scanf("%d", &tmp);
//			num ^= tmp; 
//		}
//		printf("%d\n", num); 
//	}return 0; 
//}


////给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
// 
//暴力破解
//int findPeakElement(int* nums, int numsLen) {
//    // write code here
//    int i = 0;
//    //先判断首尾
//    if (nums[0] > nums[1]) {
//        return 0;
//    }
//    if (nums[numsLen - 1] > nums[numsLen - 2]) {
//        return numsLen - 1;
//    }
//    //首尾无峰再判断中间
//    for (i = 1; i < numsLen - 1; i++) {
//        if (nums[i] > nums[i] - 1 && nums[i] > nums[i + 1]) {
//            break;
//        }
//    }
//    return i;
//}

//二分法
//找到中间元素，如果该元素大于其左边元素，则峰值在右边，如果该元素大于其右边元素则峰值在左边
//int findPeakElement(int* nums, int numsLen) {
//    // write code here
//    int i = 0;
//    //先判断首尾
//    if (nums[0] > nums[1]) {
//        return 0;
//    }
//    if (nums[numsLen - 1] > nums[numsLen - 2]) {
//        return numsLen - 1;
//    }
//    //首尾无峰再判断中间
//    int left = 0, right = numsLen - 1, mid = 0;
//    while (left < right) {
//        mid = (right + left) / 2;
//        //当mid为峰值
//        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
//            return mid;
//        }//当mid大于左边但小于右边，峰值在右边
//        else if(nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1]){
//            //移动left
//            left = mid + 1;
//        }//当mid大于右边小于左边，峰值在左边
//        else if (nums[mid] < nums[mid - 1] && nums[mid] > nums[mid + 1]) {
//            //移动right
//            right = mid - 1;
//        }
//    }
//    return i;
//}


////牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
////但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
////牛牛希望你能帮他计算一共有多少个可能的数对。
////输入描述：
////输入包括两个正整数n, k(1 <= n <= 10 ^ 5, 0 <= k <= n - 1)。
////输出描述：
////对于每个测试用例, 输出一个正整数表示可能的数对数量。
////暴力求解
//int main() {
//    int n = 0, k = 0;
//    scanf("%d %d", &n, &k);
//    int x = 1, y = 1;
//    long int count = 0;
//    for (x = 1; x <= n; x++) {
//        for (y = 1; y <= n; y++) {
//            if (x % y >= k) {
//                count++;
//                printf("(%d,%d) ",x,y);
//            }
//        }
//    }
//    printf("\n%ld", count);
//    return 0;
//}

//因为数据 x,y∈(1,n)，当 x%y>=k 时count++
// 例如 n=16 k=3
// 那么当 y<=k 时，x%y<k 恒成立
// 当 y>k && x<y ，设 y=4 在区间 (ax，ay)，a∈Z 中，x%y>=k 的个数为 y-k 个
// 而这样的区间有 n/y 个，[1,2,3,4] [5,6,7,8] [9,10,11,12] ，总数为 (n/y)*(y-k)
// 还有部分数据在区间之外[13,14,15,16]，在区间之外的数据的个数为 n%y ，如果个数小于k，则不用考虑
// 该趟总数为(n/y)*(y-k)
// 当 y=6，区间为[1,2,3,4,5,6] [7,8,9,10,11,12] [13,14,15,16]
// 此时[13,14,15,16]的元素个数大于k，则符合条件的元素为[15,16],个数为该区间的元素个数4 减去 k-1 个， 为n%y-(k-1)
// 该趟总数为 (n/y)*(y-k)+n%y-(k-1)
// 
// 所以count = count + (n/y)*(y-k)+ ((n%y<k)?0:n%y-(k-1))
//
//int main() {
//    long n, k;
//    scanf("%d %d", &n, &k);
//    if (k == 0) {
//        printf("%ld", n * n);
//    }
//    else {
//        long count = 0;
//        for (long y = k + 1; y <= n; y++) {
//            count += (n / y) * (y - k) + ((n % y < k) ? 0 : n % y - (k - 1));
//        }
//        printf("%ld", count);
//    }
//    return 0;
//}


////输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出
//int main() {
//    char str[1000];
//    scanf("%s", str);
//    int k = 0;
//    scanf("%d", &k);
//    int i = 0;
//    for (i = 0; i < k; i++) {
//        printf("%c", str[i]);
//    }
//    return 0;
//}

//int main() {
//    char str[1000];
//    scanf("%s", str);
//    int k = 0;
//    scanf("%d", &k);
//    str[k] = '\0';
//    printf("%s", str);
//    return 0;
//}